package com.yoshino.leetcode.improve40.Threetyeighth;

import java.util.*;

class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        // 广度搜索
        int n = equations.size();
        // 使用 Floyd 算法，预先计算出任意两点之间的距离。
        Map<String, Integer> variables = new HashMap<>();
        // 我们首先需要遍历 equations 数组，找出其中所有不同的字符串，并通过哈希表将每个不同的字符串映射成整数。
        // 以便后续建图
        int nvars = 0;
        for (int i = 0; i < n; i++) {
            if (!variables.containsKey(equations.get(i).get(0))) {
                variables.put(equations.get(i).get(0), nvars++);
            }
            if (!variables.containsKey(equations.get(i).get(1))) {
                variables.put(equations.get(i).get(1), nvars++);
            }
        }
        // 建图，存 i / j 的值
        double[][] graph = new double[nvars][nvars];
        for (int i = 0; i < nvars; i++) {
            Arrays.fill(graph[i], -1.0);
        }
        // 依据 values 的值存入图中
        for (int i = 0; i < n; i++) {
            int va = variables.get(equations.get(i).get(0)), vb = variables.get(equations.get(i).get(1));
            graph[va][vb] = values[i];
            graph[vb][va] = 1.0 / values[i];
        }
        // 计算所有值
        for (int k = 0; k < nvars; k++) {
            // 以 k 点为中转站
            for (int i = 0; i < nvars; i++) {
                for (int j = 0; j < nvars; j++) {
                    if (graph[i][k] > 0 && graph[k][j] > 0) {
                        // 已赋值过
                        graph[i][j] = graph[i][k] * graph[k][j];
                    }
                }
            }
        }
        int resSize = queries.size();
        double[] res = new double[resSize];
        for (int i = 0; i < resSize; i++) {
            List<String> query = queries.get(i);
            if (variables.containsKey(query.get(0)) && variables.containsKey(query.get(1))) {
                int a = variables.get(query.get(0)), b = variables.get(query.get(1));
                res[i] = graph[a][b];
            } else {
                res[i] = -1;
            }
        }
        return res;
    }

    public int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public int rows, columns;

    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        rows = matrix.length;
        columns = matrix[0].length;
        int[][] keep = new int[rows][columns];
        int res = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                res = Math.max(res, dfs(matrix, i, j, keep));
            }
        }
        return res;
    }

    private int dfs(int[][] matrix, int row, int col, int[][] keep) {
        if (keep[row][col] != 0) {
            // 记录过
            return keep[row][col];
        }
        keep[row][col]++;
        for (int[] dir : dirs) {
            int nrow = row + dir[0], ncol = col + dir[1];
            if (nrow >= 0 && nrow < rows && ncol >= 0 && ncol < columns && matrix[nrow][ncol] > matrix[row][col]) {
                keep[row][col] = Math.max(keep[row][col], dfs(matrix, nrow, ncol, keep) + 1);
            }
        }
        return keep[row][col];
    }


    // 存储有向图
    List<List<Integer>> edges;
    // 标记每个节点的状态：0=未搜索，1=搜索中，2=已完成
    int[] visited;
    // 用数组来模拟栈，下标 n-1 为栈底，0 为栈顶
    int[] result;
    // 判断有向图中是否有环，有环则无解
    boolean valid = true;
    // 栈下标
    int index;

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<>());
        }
        visited = new int[numCourses];
        result = new int[numCourses];
        index = numCourses - 1;
        for (int[] prerequisite : prerequisites) {
            // [1,0]：先修完0；0 -> 1
            edges.get(prerequisite[1]).add(prerequisite[0]);
        }
        // 每次选择一个 未搜索 的节点，深度遍历
        for (int i = 0; i < numCourses && valid; i++) {
            if (visited[i] == 0) {
                dfs(i);
            }
        }
        if (!valid) {
            return new int[0];
        }
        return result;
    }

    private void dfs(int ind) {
        visited[ind] = 1;
        // 搜索相邻节点，有环则退出
        for (int v : edges.get(ind)) {
            if (visited[v] == 0) {
                dfs(v);
                if (!valid) {
                    return;
                }
            } else if (visited[v] == 1) {
                // 搜索中，表示出现环
                valid = false;
                return;
            }
        }
        visited[ind] = 2;
        // 后修
        result[index--] = ind;
    }

}